package com.LeeCode;

import java.util.*;

/**
 * 有向图中最大颜色值
 */

public class Code1857 {
    public static void main(String[] args) {

    }

    public int largestPathValue(String colors, int[][] edges) {
        char[] cs = colors.toCharArray();
        int n = cs.length;

        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] deg = new int[n];

        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            if (x == y) { // 自环
                return -1;
            }
            g[x].add(y);
            deg[y]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) {
                q.add(i); // 入度为 0 的点入队
            }
        }

        int ans = 0;
        int visited = 0;
        int[][] f = new int[n][26];

        while (!q.isEmpty()) {
            int x = q.poll(); // x 的所有转移来源都计算完毕，也都更新到 f[x] 中
            visited++;
            int ch = cs[x] - 'a';
            f[x][ch]++;
            ans = Math.max(ans, f[x][ch]);
            for (int y : g[x]) { // 遍历当前位置的所有邻居
                for (int i = 0; i < 26; i++) {
                    f[y][i] = Math.max(f[y][i], f[x][i]); // 刷表法，更新邻居的最大值
                }
                if (--deg[y] == 0) {
                    q.add(y);
                }
            }
        }

        return visited < n ? -1 : ans;
    }
}
